package com.wrial.offer;
/*
 * @Author  Wrial
 * @Date Created in 15:00 2020/3/31
 * @Description 面试题55 - II. 平衡二叉树    使用到求树的最高高度，如果两个子树相差大于1就不是平衡的
 */

public class FaceTest_55_II {

    public boolean isBalanced(TreeNode root) {

        if(root == null) return true;
        // 如果左右最大深度大于1就不平衡
        if(Math.abs(maxDepth(root.left)-maxDepth(root.right))>1){
            return false;
        }
        // 向下递归
        return isBalanced(root.left) && isBalanced(root.right);

    }
    public int maxDepth(TreeNode root){
        if(root == null) return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }


}
